/*# 编程题

## 题目

假设我们有一个不包含重复元素的正整数素组 coins，表示各种面额的硬币（这些面额的硬币的个数不限），以及一个正整数 n，表达要用这些硬币找的钱。编写一个函数，计算用这些硬币可以正好找出 n 的方法。

## 示例

例如：

* `coins` 等于 `[1, 5, 10, 25]`，表示我们有四种面额的硬币；
* `n` 等于 10，表示我们要用上面四种硬币找 10 元钱；

一种有多少方法呢？答案是四种：

* 1 x 10
* 2 x 5
* 1 x 5 + 5 x 1
* 10 x 1

因此，我们的函数应该返回 4。

## 解答
[2,5]
1 0 1 0 1 0 1 0 1 0 1  = ways
0 1 2 3 4 5 6 7 8 9 10 = i

2 <= 1 F pass 
2 <= 2 T 2-2=0
2 <= 3 T 3-2=1 
2 <= 4 T 4-2=2
2 <= 5 T 5-2=3
2 <= 6 T 6-2=4
2 <= 7 T 7-2=5
....

------------------------------------------
[2,5]
1 0 1 0 1 1 1 1 1 1 2
0 1 2 3 4 5 6 7 8 9 10

5 <= 1 F pass 
5 <= 2 F pass 
5 <= 3 F pass  
5 <= 4 F pass 
5 <= 5 T 5-5=0
5 <= 6 T 6-5=1
5 <= 7 T 7-5=2

尝试根据函数中的提示，完成代码：
*/
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int numberOfWaysToMakeChange(vector<int> coins, int n)
{
    // 创建一个包含 n+1 的元素的数组 ways，表达找从 0 至 n 钱的方法。
    // 并且将ways中每个元素初始化为0
    vector<int> ways(n + 1, 0);

    // ++++++中心思想++++++
    // 要计算n相对于面额k的找钱方法，只需计算n-k的相对于面额k的方法数，以此类推
    // 理解当面额k为面额数组k[k1,k2,...kn]时，那么计算n相对于面额数组k的找钱方法，只需计算n-k的相对于面额数组k的方法数，以此类推
    // ++++++中心思想++++++

    // 遍历所有的面额
    // 对于每一种面额，我们用它去遍历所有要找的钱数
    // 如果能找
    //    更新对应找钱上的方法数 ways[b(找钱)] + ways[b(找钱) - a(面额)]
    // 否则
    //    PASS
    // 所有面额遍历结束，ways 最后一个元素的值，就是答案

    //初始化ways[0]为1，表示找钱0即找开了，记1次
    ways[0] = 1;

    //循环每一种面额
    for (int j = 0; j < coins.size(); j++)
    {
        //循环计算1到n中所有数的相对于一种面额的找钱情况
        for (int i = 1; i <= n; i++)
        {
            //如果面额小于要找开的钱数
            if (coins[j] <= i)
            {
                //累加:把要找钱i的方法数和i-coins[j]的找钱方法数加起来
                ways[i] = ways[i] + ways[i - coins[j]];
            }
                
        }
        //打印每一种面额计算完成后ways中的值
        for (int k = 0; k < ways.size(); k++)
        {
            cout << k << "=" << ways[k] << endl;
        }

        //打印“--”用作分隔，便于查看ways中间值
        cout << "----------------------------------------" << endl;

    }
    
    //返回ways中最后一个元素的值，即是我们要计算要找钱n的方法数
    return (*(ways.end() - 1));
}

int main(int argc, char const *argv[])
{
    //定义一个整型变量n
    int n;
    
    //在屏幕上打印put in
    cout << "put in:";

    //将屏幕上的输入数字保持在变量n里
    cin >> n;

    //定义一个整型数组变量coins，数组里初始化1，5，10，25 四个数字，表示4种面额
    vector<int> coins = {5, 1};
    
    //打印出整型数组变量coins里的所有值，用空格分隔
    for (int i = 0; i < coins.size(); i++)
    {
        cout << coins[i] << " ";
    }
    
    //打印一个换行符
    cout << endl;

    //定义一个整型变量res，同时调用函数numberOfWaysToMakeChange，把
    //numberOfWaysToMakeChange的返回值，初始化赋值给res
    int res = numberOfWaysToMakeChange(coins, n);

    //在屏幕上打印“result:”和res的值
    cout << "result: " << res << endl;

    //main函数返回，返回值为0
    return 0;
}